package com.jiang.专题.动态规划.Q122;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/01 22:19
 */
class Solution {
    // 贪心
    // public int maxProfit(int[] prices) {
    //     int res = 0;
    //     int n = prices.length;
    //     for (int i = 1; i < n; ++i) {
    //         res += Math.max(0, prices[i] - prices[i - 1]);
    //     }
    //     return res;
    // }

    // 动态规划
    // public int maxProfit(int[] prices) {
    //     int len = prices.length;
    //     int[] temp = new int[len];  // 表示从当前开始直到数组最后的的最大盈利（第i天之后最大盈利）
    //     // 从后往前遍历每一天
    //     for (int i = len - 2; i >= 0; i--) {
    //         int differ = 0; // 当天与后面任意一天盈利最大值
    //         // 从天数 i 开始往后遍历，求得天数 i 盈利temp[i]最大值
    //         for (int j = i + 1; j < len; j++) {
    //             differ = Math.max(differ, prices[j] - prices[i]);
    //             // 天数 i 与天数 j 的盈利 + 天数 j 的最大盈利 是否大于最大盈利
    //             temp[i] = Math.max(temp[i], differ + temp[j]);
    //         }
    //     }
    //     return temp[0];
    // }
    // public int maxProfit(int[] prices) {
    //     int len = prices.length;
    //     int[] dp = new int[len]; // dp[i]表示第i天之前的最大盈利
    //     for (int i = 1; i < len; ++i) {
    //         for (int j = 0; j < i; j++) {
    //             int diff = prices[i] - prices[j];
    //             if (diff > 0) {
    //                 dp[i] = Math.max(dp[i], diff + dp[j]);
    //             } else {
    //                 dp[i] = Math.max(dp[i], dp[j]);
    //             }
    //         }
    //     }
    //     return dp[len - 1];
    // }

    public int maxProfit(int[] prices) {
        int dp0 = 0;  // 当天不持有股票的最大盈利
        int dp1 = -prices[0]; // 当天持有股票的最大盈利
        for (int i = 1; i < prices.length; ++i) {
            int newDp0 = Math.max(dp0, dp1 + prices[i]); // 当天不持有股票盈利为 前一天不持有股票最大盈利或卖掉前一天持有股票最大盈利 这两个最大值
            int newDp1 = Math.max(dp1, dp0 - prices[i]);// 当天持有股票盈利为 前一天持有股票最大盈利或前一天不持有股票最大盈利 + 买几天股票 这两个最大值
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
}
